%----------------------------------------------------------------------------------------
%	CHAPTER 9
%----------------------------------------------------------------------------------------

\chapter{目标代码及其生成}

什么是目标代码？目标代码在编译器中起到什么作用呢？

目标代码是指在机器上可以运行的代码，在本章中，可以视作汇编指令。目标代码生成，是编译的最后一个阶段，其功能可表示如下图\ref{fig:9-1}。

%-------------------------------------------
\begin{figure}[htbp]
\centering
  \input{chapter9/figures/figure-fun_of_last_step_in_compiling}
	\caption{目标代码功能}
	\label{fig:9-1}
\end{figure}
%-------------------------------------------

目标代码的来源是中间代码，也有从源程序直接生成目标代码的编译器（解释器），本书中介绍的是从中间代码进行转化的目标代码。为了简化教学内容，在生成目标代码时忽略了值单元地址，因此符号表甚少出现，但在实际生成编译器时，符号表对于生成目标代码十分重要。

其中，\textbf{中间代码}的种类是多样的，包括第7章中介绍的逆波兰式、三元式、四元式、语义树等；\textbf{目标代码}包括机器语言，汇编语言等，高级语言也可以作为目标代码，如：代码移植。为了便于讲解，本章中的目标代码是汇编语言的一个虚拟指令集，并不能直接运行，但原理是一致的；\textbf{符号表}包括变量的语义词典等，在生成目标代码时，会访问符号表来获取变量地址等信息。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{目标代码生成的基本问题}

\subsection[目标代码选择]{目标代码选择}

目标代码生成任务的目的是生成在机器上可以执行的指令。首先要考虑选择什么作为目标代码？

大多数编译程序不产生绝对地址的机器代码，而是以\textbf{汇编语言程序}作为输出，因为汇编代码与机器指令是相互对应的，以汇编语言程序作为输出可以使代码生成阶段变得容易。此外，\textbf{指令集的选择}以及\textbf{指令的执行速度问题}都是重要因素。为了使算法具有通用性，这里采用的是类似于8086的虚拟机及其指令系统，选择原因如下：

(1)	直接生成机器代码，难度较大，且对于不同的架构，机器代码也有所区别；

(2)	希望选择一种相对抽象但又能够理解的指令，汇编语言就具备这一属性；

(3)	不希望过于复杂，复杂可能会影响程序执行效率，即使有较好的可读性，细节上也不便于进行操作。
\\
$\bigstar$\textbf{虚拟机及其指令系统：}

%------------------------------------------------
\begin{enumerate} 
\item \textbf{虚拟机寄存器: }$\rm R_0, R_1, \dots , R_{n-1}$

 现代CPU的计算，严格意义上来说，都是在寄存器中完成，CPU不能直接操作内存或外存上的数据，只能操作寄存器中的内容，因此内存或外存上的数据，只有转到寄存器中，CPU才能对其进行操作。
\item \textbf{虚拟机指令系统：}
\\
(1)	指令的基本形式：$\rm {op}\ R_i,\ R_k/M$。
\\
其中op表示操作码，可以理解为指令的一种方式，如加减乘除；M表示变量的内存地址；$\rm R_i/R_k$表示寄存器地址。
\\
“$\rm{op} \ R_i,\ R_k$”的含义是“$\rm R_i:= (R_i)\ op\ (R_k)$”，表示Ri寄存器里的内容，和$R_k$寄存器里的内容，通过$\rm{op}$运算，结果存在$\rm R_i$寄存器中；
\\
\textbf{注意：}
\\
\ding{172}$\rm R_i$寄存器里的内容参与运算，且结果保存在$\rm R_i$中，即$\rm R_i$中原来的值被结果覆盖了。
\\
\ding{173}如果$\rm{op}$为单目运算，含义是“$\rm R_i:= op\ (R_k/M)$”,表示通过op运算，操作$\rm R_k$寄存器里的内容或M地址指向的内容，结果存在$\rm R_i$寄存器中。
\\
(2)	常用的指令：
\\
\ding{172}取数据、存数据：8086中存、取指令均为move，这里为了做区分，取数据用LD，存数据用ST。

LD $\rm R_i,\ R_k/M$ ——表示从$\rm R_k/M$取到的数据存入$\rm R_i$中，写作$\rm R_i:=(R_k/M)$

ST $\rm R_i,\ R_k/M$ ——表示将$\rm R_i$中的内容存入$\rm R_k/M$中，写作$\rm R_k/M := (R_i)$

\ding{173}转向操作：FJ表示假跳，TJ表示真跳，JMP表示无条件跳转。

FJ $\rm R_i,\ M$ ——表示判断$\rm R_i$中内容是否为假，为假，则跳转到M地址指向的代码

TJ $\rm R_i,\ M$ ——表示判断$\rm R_i$中内容是否为真，为真，则跳转到M地址指向的代码

JMP \_\_, M ——表示无条件跳转到M地址指向的代码

\ding{174}算术运算：与8086指令类似，包含ADD(加)、SUB(减)、MUL(乘)、DIV(除)

ADD $\rm R_i,R_k/M\ ——R_i:=(R_i)+(R_k/M)$

SUB $\rm R_i,R_k/M\ ——R_i:=(R_i)-(R_k/M)$

MUL $\rm R_i,R_k/M\ ——R_i:=(R_i)*(R_k/M)$

DIV $\rm R_i,R_k/M\ ——R_i:=(R_i)/(R_k/M)$

此外，还有很多操作码op，在具体实现时，可以自行定义。

\ding{175}逻辑运算

LT (<), GT (>), EQ (==), LE (<=), GE (>=), NE (!=)

AND (\& \&), OR (||), NO (!)

\end{enumerate} 

介绍完指令集，接下来介绍目标代码生成。四元式序列是不需要进一步解析的单操作，目标指令集确定时，从中间代码到目标代码，实际上是一个\textbf{模板}翻译的过程。

高级程序设计语言，即使程序非常复杂，但指令的种类是有限的，四元式也是如此，包括运算四元式、赋值四元式、跳转四元式等。

(1) \textbf{运算四元式}。若有四元式($\omega, a, b, t$)，表示$a$和$b$进行$\omega$操作，结果单元放到$t$中。依据前面介绍的指令集，替换成目标代码时，运算对象放到寄存器中再进行运算。生成三条目标代码如下：

\begin{tabular}{crll}
\ding{172}& LD &R, &$a$ \\

\ding{173}& $\widetilde{\omega}$ &R, &$b$ \\

\ding{174}& ST &R, &$t$
\end{tabular}

第一条表示将$a$取到寄存器R中；

第二条表示寄存器中内容与$b$发生$\rm \omega$运算，结果在R中;

第三条表示将R中内容保存到$t$中。对于加法，只需将$\rm \omega$替换为ADD。显然，如果不考虑代码优化，这是一个模板替换的过程。 

(2) \textbf{赋值四元式}。若有四元式(=, $a$, \_\_, $b$)，对应的目标代码如下。

\begin{tabular}{clll}
\ding{172}& LD &R, &$a$\\

\ding{173}& ST &R, &$b$\\
\end{tabular}

因为指令集中没有内存单元存到内存单元的操作，所以\ding{172}第一条先将$a$取到寄存器R中；\ding{173}第二条将寄存器R的内容保存到$b$中。

%----------------------------------------------

\begin{example}
据下列四元式翻译目标代码：

\begin{tabular}{lcccr}
(1) &( $+$ & $a$ & $b$ & $t_1$  ) \\

(2) &( $-$ & $t_1$ & $d$ & $t_2$ )
\end{tabular}

解法1：若完全依据\textbf{模板}，将生成如下6条目标指令。

\begin{tabular}{clll}
\ding{172}& LD &R, &$a$ \\

\ding{173}& ADD &R, &$b$ \\

\ding{174}& ST &R, &$t_1$ \\

\ding{175}& LD &R, &$t_1$ \\

\ding{176}& SUB &R, &$d$ \\

\ding{177}& ST &R, &$t_2$
\end{tabular}

下一步考虑能否进行优化。这6条中，有两条做了无用功，第3条将寄存器R中内容保存到$t_1$，紧接着第4条将$t_1$中的内容取到寄存器R中，这两条可以省去。相当于第1条四元式生成的目标代码中省去了模板的最后一条，第2条四元式生成的目标代码省去了模板中的第一条，不难发现运算四元式对应模板中第二条必不能省去，另两条可根据情况进行删减，如当一条四元式的结果单元，是下一条四元式的第一运算对象时。但不能简单地省去，否则若后续还有用到$t_1$的操作，将无法进行。如果不省ST R, $t_1$，$a+b$的结果存入了$t_1$，如果后面用到$t_1$，也可以取到相应值。$t_1$后续是否会被使用，决定了是否要将$t_1$存入内存单元。应用该模板，最好的优化结果是只保留第二条，最差的结果是三条都保留。

为了精简代码，四元式结果变量值不急于存储。生成目标代码时，可以先生成前两条，第三条目标代码滞后生成。例如在生成($ +\ \ a\ \ b\ \ t_1$)对应的目标代码时，先生成前两条，再根据后一条四元式决定是否生成最后一条四元式。

解法2：第(1)个四元式表示将$a$和$b$相加，结果放在$t_1$。$a$和$b$是变量，符号表中记录的变量地址是内存地址，CPU运算需要在寄存器上操作，因此需要先将运算对象$a$取到寄存器$\rm R_0$中，从而通过ADD指令对$\rm R_0$和$b$变量对应的内容进行计算，结果放在$\rm R_0$中。

第(2)个四元式表示$t_1$减去$d$，结果放在$t_2$。经过上一步计算，$t_1$存在$\rm R_0$中，可以直接使$\rm R_0$中的内容减去$d$变量对应内容，即SUB $\rm R_0$, $d$, $\rm R_0$寄存器中内容为$t_2$。

\begin{tabular}{clll}
\ding{172}& LD &$\rm R_0$, &$a$ \\

\ding{173}& ADD &$\rm R_0$, &$b$ \\

\ding{174}& SUB &$\rm R_0$, &$d$
\end{tabular}
\label{ex:9-1}
\end{example}
%----------------------------------------------

%----------------------------------------------

\begin{example}
根据下列四元式翻译目标代码：

\begin{tabular}{ccccr}
(1) &( $+$& $a$  &$b$ & $t_1$  ) \\

(2) &( $-$ &$c$  &$d$ & $t_2$  ) \\

(3) &( $*$ &$t_1$ & $t_2$ & $t_3$  )
\end{tabular}

解：依照例9.1解法1的分析，先生成($ +\ \ a\ \ b\ \ t_1$)对应的前两条目标代码，第三条ST滞后生成。处理下一条四元式，两个操作数与$t_1$均不相关，一种处理方式是将$\rm R_0$寄存器中的内容保存到$t_1$中，生成ST指令，然后用$\rm R_0$寄存器做$c-d$的运算，这种方式应用于单寄存器；若有多个寄存器可以选择，可以选$\rm R_1$寄存器进行第二条四元式的运算，同样的，模板中的第三条指令滞后生成。再看第三条四元式，来决定前两条四元式的目标代码中的ST指令是否生成，发现第三条四元式用到了前两条四元式的结果单元，前两条四元式的ST指令均可省去，直接生成乘法操作的目标代码。生成目标代码如下：

\begin{tabular}{cllc}
\ding{172}& LD &$\rm R_0$,&$a$ \\

\ding{173}& ADD& $\rm R_0$, &$b$ \\

\ding{174}& LD &$\rm R_1$, &$c$ \\

\ding{175}& SUB &$\rm R_1$, &$d$ \\

\ding{176}& MUL &$\rm R_0$,& $\rm R_1$
\end{tabular}

【讨论】在真正算法实现时，还需要解决一些问题：

(1)	为了精简代码，四元式结果变量值并不急于存储。上例中没有将$t_1$、$t_2$、$t_3$的值存入内存中，而是放在寄存器中。

(2)	例9.1中的$t_1$的值，系统如何知道是在寄存器$\rm R_0$中？

(3)	例9.2存在寄存器分配问题，显然，若$t_2$仍然占用寄存器$\rm R_0$，则$t_1$值将被覆盖。例子中假设有多个寄存器，如果是单寄存器，需要先保存$\rm R_0$中的内容，再进行下一步操作。
\label{ex:9-2}
\end{example}
%----------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{变量的活跃信息}

为了解决上一节的问题，介绍一个重要概念——\textbf{活跃信息}，定义的是一个变量在一个基本块或一段程序内被使用的情况。具体来说需要引入变量的定义点和应用点，来判断一个变量是否活跃。

例9.2中的$t_1$，如果在接下来还会被用到，那它就是活跃的，可能需要执行ST指令；如果$t_1$在接下来都不会再被用到，那它就是不活跃的，它所在的寄存器$\rm R_0$就可以让给其他变量。

\begin{enumerate}
\item \textbf{变量的定义点和应用点}
设有四元式：q ($\omega$ B C A)

应用点和定义点是相对一个四元式而言的，变量B和C是操作数，在四元式q中被使用，则称B和C在四元式q处有应用点(q)；A是结果单元，在四元式q中对A进行赋值，即给A一个新的定义，则称A在四元式q处有定义点(q)。

利用定义点和应用点的概念，确定一个变量是否为活跃变量。

\item \textbf{活跃变量与非活跃变量}
\textbf{活跃变量：}一个变量从某时刻(q)起，到下一个定义点止，期间若有应用点，则称该变量在q是活跃的\rm (y)，否则称该变量在q是非活跃的(n)。活跃和非活跃是相对某一时刻而言，脱离时刻概念，讨论活跃和非活跃也就没有意义。

注意，我们是在一个基本块内讨论变量的活跃信息的，基本块既是优化的基本单位，也是目标代码生成的基本单位，还是求取活跃信息的基本单位。为了方便处理，假定：

(1)	临时变量在基本块出口后是非活跃的(n)；在基本块结束后，临时变量不会再被使用。

(2)	非临时变量在基本块出口后是活跃的\rm (y)；在基本块结束后，非临时变量会再被使用。

这样的约定，可能不是最高效的，但却是最安全的。不会将活跃变量误认为非活跃变量，而没有及时更新信息，产生错误。

以一个赋值语句为例，中间进行算术运算时，产生的临时变量到赋值完成后都不会再被使用。下面通过具体例子说明变量的活跃信息求解过程。

%----------------------------------------------
\begin{example}
求下述基本块内变量的活跃信息：
$x=(a+b)/(a*(a+b));i=a+b;$
解：令A(I)中的I为变量A在某点的活跃信息(y/n)。

第一步，写出四元式序列:

\begin{tabular}{ccccr}
\ding{172}&( $+$ & $a$ & $b$ & $t_1$ ) \\

\ding{173}&( $+$ & $a$ & $b$ & $t_2$ ) \\

\ding{174}&( $*$ & $a$ & $t_2$ & $t_3$ ) \\

\ding{175}&( $/$ & $t_1$ & $t_3$ & $t_4$ ) \\

\ding{176}&( $=$ & $t_4$ & \_\_ & $x$ ) \\

\ding{177}&( $+$ & $a$ & $b$ & $t_5$ ) \\

\ding{178}&( $=$ & $t_5$ & \_\_ & $i$ )
\end{tabular}

第二步，进行DAG优化，得到优化后的四元式:

\begin{tabular}{ccccr}
\ding{172}&( $+$ & $a$ & $b$ & $t_1$ ) \\

\ding{173}&( $*$ & $a$ & $t_1$ & $t_3$ ) \\

\ding{174}&( $/$ & $t_1$ & $t_3$ & $x$ ) \\

\ding{175}&( $=$ & $t_1$ & \_\_ & $i$ )
\end{tabular}

第三步，填写活跃信息。

对于第一个四元式中变量$a$，根据定义，看$a$到下一个定义点之间是否有应用点。发现没有下一个定义点，又因为$a$是用户定义变量，在基本块出口，第四个四元式执行完后是活跃的，认为第四个四元式后还有变量$a$的定义点，且到这个定义点之间还有$a$的应用点。在第四个四元式之后使用变量$a$，变量$a$是活跃的，在第一个到第四个四元式之间的变量$a$当然也是活跃的，活跃信息填\rm (y)。

对于第一个四元式中变量$b$，虽然在第二个四元式到第四个四元式之间没有使用，但是根据前面对于变量$a$的分析，变量$b$是用户定义变量，在基本块出口时是活跃的，因此活跃信息填\rm (y)。

对于第一个四元式中变量$t_1$，在第一个四元式中被定义，在第二个四元式中被使用，$t_1$是活跃的，活跃信息填\rm (y)。

同理，根据变量在下一定义点前是否被使用，并结合基本块出口处的活跃信息，附有活跃信息的四元式如下。其中对于第三个四元式中变量$t_3$，在第四个四元式中没有$t_3$出现，$t_3$在这个基本块内不能再被使用，在第四个四元式之后，因为$t_3$是临时变量，基本块出口后是非活跃的，即$t_3$在第四个四元式之后不会再被使用，因此第三个四元式中变量$t_3$是非活跃的，活跃信息填(n)。同理第四个四元式中变量$t_1$也是非活跃的。

\begin{tabular}{ccccr}
(1) &( $+$ & $a$(\textcolor{red}{y}) & $b$(\textcolor{red}{y}) & $t_1$(\textcolor{red}{y}) ) \\

(2)& ( $*$ & $a$(\textcolor{red}{y}) & $t_1$(\textcolor{red}{y}) & $t_3$(\textcolor{red}{y}) ) \\

(3) &( $/$ & $t_1$(\textcolor{red}{y}) & $t_3$(\textcolor{blue}{n}) & x(\textcolor{red}{y}) ) \\

(4) &( $=$ &$t_1$(\textcolor{blue}{n}) & \_\_ & $i$(\textcolor{red}{y}) )
\end{tabular}
\label{ex:9-3}
\end{example}
%----------------------------------------------

\item \textbf{基本块内活跃信息求解的算法}
$\bigstar$ 数据结构支持:

(1)	在符号表上增设一个信息项(L)用以记录活跃信息，结构如下。活跃信息是动态的，与时刻相关，信息项辅助填写活跃信息。

%-------------------------------------------
\begin{figure}[htbp]
\centering
  \input{chapter9/figures/figure-algo_for_solving_active_info_in_basic_blk_step1}
  \caption{记录活跃信息的信息项}
	\label{fig:9-2}
\end{figure}
%-------------------------------------------

(2)	四元式中变量X的附加信息项X(L)，取值L=n/y，表示不活跃/活跃；

$\bigstar$ 算法：

(1)	初值：基本块内各变量SYMBL[X(L)]分别填写：若X为非临时变量，则置X\rm (y)，否则置X(n)。y/n表示活跃/不活跃，目的是初始化为基本块出口的状态。

(2)	\textbf{逆序}扫描基本块内各四元式（设为q: (ω B C A)）：

执行：

\ding{172} QT[\textcolor{red}{q: A(L)}]:= SYMBL[\textcolor{blue}{A(L)}];，对于结果单元A，读取符号表中变量A的附加信息项，作为四元式中结果单元A的活跃信息。

\ding{173} SYMBL[\textcolor{blue}{A(L)}]:= \textcolor{blue}{(n)};，将符号表中变量A的附加信息项置为n（非活跃）。

\ding{174} QT[\textcolor{red}{q: B, C(L)}]:= SYMBL[\textcolor{blue}{B, C(L)}];，对于运算对象B、C，同样读取符号表中对应变量的附加信息项，作为四元式中B、C的活跃信息。

\ding{175} SYMBL[\textcolor{blue}{B, C(L)}]:= \textcolor{blue}{\rm (y)};，将符号表中B、C的附加信息项置为y（活跃）。

以此类推，逆序扫描基本块内各个四元式，直到基本块的第一个四元式。虽然活跃信息的定义是一个正序的定义，但算法填写活跃信息，是逆序填写，从基本块出口状态入手，反向进行。如果出现定义点，则定义点之前活跃信息为n，如果出现应用点，则应用点前不到定义点的时刻，活跃信息为y。

下面通过活跃信息生成过程示例进一步说明上述算法。

%----------------------------------------------

\begin{example}
根据基本块内四元式序列，填写活跃信息:

解：

第一步，初始化符号表中的附加信息项如图\ref{fig:9-3}。对非临时变量，初始化为y，对临时变量初始化为n。

%-------------------------------------------
\begin{figure}[htbp]
\centering
  \input{chapter9/figures/figure-algo_for_solving_active_info_in_basic_blk_exp1_step1}
  \caption{初始化附加信息项}
	\label{fig:9-3}
\end{figure}
%-------------------------------------------

第二步，逆序扫描四元式，填写活跃信息。

第(6)个四元式，对于结果单元$x$，从符号表中取得$x$的附加信息项内容，作为x的活跃信息，并将符号表中$x$的附加信息项置为n，这是$x$的定义点，在定义点之前且没有应用点，$x$是非活跃的。类似地，填写$t_4$、$t_5$的活跃信息，先从符号表中取得附加信息项内容作为对应变量的活跃信息，然后将符号表中的附加信息项置为y，$t_4$、$t_5$被使用，则在之前也是活跃的。

第(5)个四元式，对于结果单元$t_5$，从符号表中取得$t_5$的附加信息项内容，作为的它活跃信息，并将符号表中$t_5$的附加信息项置为n。对于$t_1$，活跃信息填从符号表中取得的附加信息项内容，并将符号表中修改为y。

第(4)个四元式，对于结果单元$t_4$，取符号表中的附加信息项，作为活跃信息，并将符号表中的附加信息项置为n。对于运算对象$a$和$t_3$，取符号表中的附加信息项，作为活跃信息，并将符号表中的附加信息项置为y。

类似地，得到活跃信息结果如下图\ref{fig:9-4}。

%-------------------------------------------
\begin{figure}[htbp]
\centering
  \input{chapter9/figures/figure-algo_for_solving_active_info_in_basic_blk_exp1_step2}
  \caption{活跃信息填表结果}
	\label{fig:9-4}
\end{figure}
%-------------------------------------------

用户定义变量大多数情况下是活跃的，但如果对同一变量两次赋值之间，没有进行使用，用户定义变量就会是非活跃的。
\label{ex:9-4}
\end{example}

%----------------------------------------------

\end{enumerate}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{寄存器的分配问题}

目标代码生成部分，目标指令的生成是根据模板进行，不是重难点，重点和难点在于优化。优化中一个很重要的内容，就是对寄存器使用的优化，即寄存器分配问题。寄存器在整个计算机体系，在编译器设计中十分重要，因为寄存器操作快且指令短，从寄存器中取数据远快于从内存或外存中取数据。

系统需要知道当前寄存器中存储的变量，或者说一个变量是否在寄存器中，在哪一个寄存器中。

\begin{enumerate}
\item \textbf{设置描述表RDL($\rm R_0$, $\rm R_1$, \dots, $\rm R_n$)}
用以记录寄存器的当前状态，如RDL.${\rm R_1}=x$，即指明当前变量x值在寄存器$\rm R_1$中。
\item \textbf{寄存器分配三原则：}
设当前四元式：q: A = B $\omega$ C，为A分配寄存器有以下三种情况：

(1)	\textbf{主动释放}。如果B已经在寄存器$\rm R_i$中，则选择$\rm R_i$；若$\omega$可交换，也可考虑C所在寄存器。

\ding{172} 若B活跃，即在下个定义点前存在应用点，则要保存B的值，方法是：若有空闲寄存器$\rm R_j$，则要将Ri中的B保存到$\rm R_j$中，生成指令ST $\rm R_i$, $\rm R_j$；否则暂时存到内存中，生成指令ST $\rm R_i$, B。若B不活跃，就不用保存B的值，不生成相关指令。

\ding{173} 修改描述表：删除B，填写A。

(2)	\textbf{选空闲者}。从空闲寄存器中选一$\rm R_i$；并把A填入描述表。

(3) \textbf{强迫释放}。剥夺一$\rm R_i$：处理办法同规则(1)。

以($\omega$ B C A)为例说明上述三条分配原则。进行$\omega$运算，需要先指定寄存器R，运算结束后，寄存器R中的值就是结果单元A的值。先确定一个寄存器作为运算寄存器，即给A分配一个寄存器。寄存器的选择有三种情况：

(1)	B在$\rm R_i$中，根据运算四元式生成的三条目标代码，第一条是将B取到寄存器中，此时B已经在寄存器中，这三条中的第一条即可省去，这种情况称为主动释放，B主动将寄存器$\rm R_i$释放给A。如果B是活跃的，要先保存B，然后再进行$\omega$运算，若有其他空闲寄存器$\rm R_j$，就生成指令ST $\rm R_i$, $\rm R_j$，否则生成ST $\rm R_i$, B；如果B不活跃，直接进行$\omega$运算。计算完成后，$\rm R_i$寄存器中保存的是A的值，因此修改描述表$\rm R_i=A$。若对于乘法和加法，第一运算对象和第二运算对象可交换时，还可以考虑主动释放寄存器C给A。

(2)	如果B不在寄存器中，乘法加法运算中C也不在寄存器中，则在空闲寄存器中选一个分配给A，并修改描述表。

(3)	如果B、C都不在寄存器中，也没有空闲寄存器，就“抢”一个寄存器，处理办法同第一种情况。怎么“抢”也有多种方法：随机抢、优先抢最不活跃的等。
\end{enumerate}

%----------------------------------------------

\begin{example}
设有三个寄存器：$\rm R_0$，$\rm R_1$，$\rm R_2$。根据给定的四元式及活跃信息，生成目标代码：

解：顺序处理四元式，根据寄存器分配三原则、活跃变量概念，写出目标代码。

%-------------------------------------------
\begin{figure}[htbp]
\centering
  \input{chapter9/figures/figure-reg_alloc_exp1}
  \caption{寄存器分配表}
	\label{fig:9-5}
\end{figure}
%-------------------------------------------

第(1)个四元式，给结果单元$t_1$分配寄存器，初始状态下三个寄存器均为空，选择寄存器$\rm R_0$，生成前两条目标代码为\ding{172}LD $\rm R_0$, $a$ \ding{173}ADD $\rm R_0$, $b$，模板中第三条指令滞后生成。修改描述表RDL，此时\textbf{$\rm R_0$保存$t_1$}，$\rm R_1$、$\rm R_2$空闲。

第(2)个四元式，给结果单元$t_2$分配寄存器，运算对象$c$和$d$都不在寄存器中，根据分配三原则“选空闲者”，将空闲寄存器$\rm R_1$分配给$t_2$，生成目标代码\ding{174}LD $\rm R_1$, c \ding{175}SUB $\rm R_1$, $d$，模板第三条指令滞后生成。修改描述表RDL，此时$\rm R_0$保存$t_1$，\textbf{$\rm R_1$保存$t_2$}，$\rm R_2$空闲。

第(3)个四元式，$t_1$和$t_2$相乘，由于$t_1$在寄存器$\rm R_0$中，根据分配三原则“主动释放”，给x分配寄存器$\rm R_0$，由于$t_1$是活跃的，需要保存，且有空闲寄存器$\rm R_2$，将$t_1$保存到$\rm R_2$，之后完成计算，生成目标代码\ding{176}ST $\rm R_0$, $\rm R_2$ \ding{177}MUL $\rm R_0$, $\rm R_1$，模板第三条仍然滞后生成。修改描述表RDL，此时\textbf{$\rm R_0$保存x}，$\rm R_1$保存$t_2$，\textbf{$\rm R_2$保存$t_1$}。

第(4)个四元式，给$y$分配寄存器，$a$不在寄存器中，此时也没有空闲寄存器，根据分配三原则“强迫释放”，因$t_2$不活跃，则剥夺$t_2$所在寄存器$\rm R_1$分配给$y$，因$t_2$不活跃，不必生成ST指令，生成目标代码\ding{178}LD $\rm R_1$, $a$，模板第二条滞后生成。修改描述表RDL，此时$\rm R_0$保存x，\textbf{$\rm R_1$保存y}，$\rm R_2$保存$t_1$。

第(5)个四元式，$a$除以$x$放在$x$中，尽管前一句将$a$放在$\rm R_1$，但根据寄存器描述表，$\rm R_1$寄存器的标志为y，认为$\rm R_1$中没有$a$。又因除法运算是不可交换的，尽管$x$在寄存器中，但不能使用$x$所在寄存器。根据分配三原则“强迫释放”，因$y$不活跃，则剥夺$y$所在寄存器$\rm R_1$分配给$x$，因$y$不活跃，不生成ST指令，生成目标代码\ding{179}LD $\rm R_1$, $a$ \ding{180}DIV $\rm R_1$, $\rm R_0$，模板第三条仍然滞后生成。\ding{178}和\ding{179}相同，后续可以进一步优化，但根据算法逻辑，会生成这样的结果。修改描述表RDL，此时\textbf{$\rm R_0$空闲，$\rm R_1$保存$x$}，$\rm R_2$保存$t_1$。

第(6)个四元式，给$y$分配寄存器，运算对象$x$在寄存器$\rm R_1$中，根据分配三原则“主动释放”，将$\rm R_1$分配给$y$，由于$x$是活跃的，需要保存，且有空闲寄存器$\rm R_0$，将$x$保存到$\rm R_0$，然后进行运算，生成目标代码\textcircled{\footnotesize 10}ST $\rm R_1$, $\rm R_0$ \textcircled{\footnotesize 11}SUB $\rm R_1$, $t_1$，模板第三条仍然滞后生成。修改描述表RDL，此时\textbf{$\rm R_0$保存$x$，$\rm R_1$保存$y$}，$\rm R_2$保存$t_1$。

第(7)个四元式，给$a$分配寄存器，运算对象$x$在寄存器$\rm R_0$中，根据分配三原则“主动释放”，将$\rm R_0$分配给$a$，由于$x$是活跃的，需要保存，且$\rm R_2$寄存器中的$t_1$不活跃，将$x$保存到$\rm R_2$中，生成目标代码\textcircled{\footnotesize 12}ST $\rm R_0$, $\rm R_2$，模板第二条滞后生成。修改描述表RDL，此时\textbf{$\rm R_0$保存$a$}，$\rm R_1$保存$y$，\textbf{$\rm R_2$保存$x$}。

填表结果如下图\ref{fig:9-6}：

%-------------------------------------------
\begin{figure}[htbp]
\centering
  \input{chapter9/figures/figure_reg_alloc_exp1_result}
  \caption{寄存器分配结果}
	\label{fig:9-6}
\end{figure}
%-------------------------------------------

在寄存器分配过程中，需要注意：

(1)	一个变量在同一时刻只能占有一个寄存器；

(2)	在基本块出口时，寄存器中的活跃变量应保存其值。

另外，寄存器分配时，是先主动释放，还是先分配空闲寄存器，这是一种算法设计，主要考虑目标代码的效率，与设计的四元式有关，可以自行调整。

如果各个寄存器中的变量都活跃，则选择一个寄存器强迫释放，并将寄存器中的变量保存到内存中，后面使用该变量时，再将其读到寄存器中。这样的访存操作，也是导致程序执行慢的主要原因。
\label{ex:9-5}
\end{example}

%----------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{目标代码生成问题}
目标代码生成是以\textbf{基本块}为单位的，在生成目标代码时要注意如下三个问题：

(1)	基本块开始时所有寄存器应是空闲的；结束基本块时应释放所占用的寄存器。

(2)	一个变量被定值（被赋值）时，要分配一个寄存器$\rm R_i$保留其值，并且要填写相应的描述表RDL.$\rm R_i$。

(3)	为了生成高效的目标代码，生成算法中要引用寄存器分配三原则和变量的活跃信息。

定义\textbf{数据结构}如下：
\begin{itemize}
\item QT[q]——四元式区：存放四元式。
\item OBJ[p]——目标区：存放目标代码。
\item RDL($\rm R_0$, $\rm R_1$, \dots, $R_n$)——寄存器状态描述表
\item SEM(m)——语义栈（用于信息暂存）：主要用于跳转指令生成目标代码时，与中间代码生成时的语义栈截然不同。
\end{itemize}

注意，这里没有考虑符号表。

具体讲解单寄存器下，一些常用四元式目标代码生成过程，包括表达式、条件语句和循环语句。

%----------------------------------------------
\begin{example}
单寄存器(R)下\textbf{表达式}目标代码生成：

设：R表示寄存器；RDL表示描述表；SEM表示语义栈。

%-------------------------------------------
\begin{figure}[htbp]
\centering
  \input{chapter9/figures/figure-obj_code_gen_exp1_2nd}
  \caption{寄存器分配表}
	\label{fig:9-7}
\end{figure}
%-------------------------------------------

解：对于表达式生成目标代码，都是顺序生成，用不到SEM结构。根据题意，仅有一个寄存器R，起始状态为空。主动释放、选空闲者、强迫释放三原则对于单寄存器的情况，没有很大意义，但仍沿用这一说法。

第(1)个四元式，给结果单元$t_1$分配寄存器R，生成目标代码\ding{172}LD R, $a$ \ding{173}ADD R, $b$。修改描述表RDL，R保存$a+b$的结果$t_1$。

第(2)个四元式，给结果单元$t_2$分配寄存器，运算对象c不在寄存器R中，由于是单寄存器，因此“强迫释放”，剥夺$t_1$所在寄存器R分配给$t_2$，且$t_1$活跃，需要保存到内存，生成ST指令。然后将$c$读到R，进行$c-d$运算，生成目标代码\ding{174}ST R, $t_1$ \ding{175}LD R, $c$ \ding{176}SUB R, $d$。修改描述表RDL，R保存$c-d$的结果$t_2$。

第(3)个四元式，给结果单元$t_3$分配寄存器，运算对象$t_1$不在寄存器R中，乘法运算可交换，运算对象$t_2$在寄存器R中，进行“主动释放”，且$t_2$不活跃，不需要保存到内存，生成目标代码\ding{177}MUL R, $t_1$。修改描述表RDL，R保存$t_1$*$t_2$的结果$t_3$。

第(4)个四元式，虽然$t_3$在寄存器中，但由于减法运算不可交换，因此“强迫释放”，先读入a再减$t_3$：将$t_3$保存到内存（减法中使用），生成ST指令。然后将a读到R，进行$a-t_3$运算，生成目标代码\ding{178}ST R, $t_3$ \ding{179}LD R, $a$ \ding{180}SUB, R, $t_3$。修改描述表RDL，R保存$a-t_3$的结果$t_4$。（此处$t_3$标注非活跃的原因，是在读$a$之前保护现场，而非运算完成后释放$t_3$）

第(5)个四元式，给结果单元$t_5$分配寄存器，运算对象$t_1$不在寄存器R中，“强迫释放”，剥夺$t_4$所在寄存器R分配给$t_5$，且$t_4$活跃，需要保存到内存，生成ST指令。然后将$t_1$读到R，进行$t_1$/2运算，生成目标代码\ding{181}ST R, $t_4$ \textcircled{\footnotesize 11}LD R, $t_1$ \textcircled{\footnotesize 12}DIV R, 2。修改描述表RDL，R保存$t_1$/2的结果$t_5$。

第(6)个四元式，与(3)类似，给x分配寄存器，加法运算可交换，运算对象$t_5$在寄存器R中，“主动释放”，生成目标代码\textcircled{\footnotesize 13}ADD R, $t_4$。

填表结果如下图\ref{fig:9-8}：

%-------------------------------------------
\begin{figure}[htbp]
\centering
  \input{chapter9/figures/figure-obj_code_gen_exp1_6th}
  \caption{寄存器分配结果}
	\label{fig:9-8}
\end{figure}
%-------------------------------------------

表达式的目标代码是顺序生成的，比较容易理解，接下来介绍带跳转语句的目标代码生成。
\label{ex:9-6}
\end{example}

%----------------------------------------------

%----------------------------------------------

\begin{example}
单寄存器(R)下，\textbf{条件语句}目标代码生成：
给定程序段如下，生成目标代码。

$\text{if} (a > b) x = (a + b) * c;$
$\text{else}\ x = 5 - a * b$

解：SEM栈用于保存待返填地址，具体实现可采用栈或队列的结构，本书中采用栈的形式进行说明。

第一步，生成四元式序列，划分基本块并标注活跃信息。基本块划分时，跳转到的语句，及跳转的下一条语句都是基本块的开始，并要求程序入口也是基本块的开始。在基本块入口和出口时，要保证寄存器是空闲的。

%-------------------------------------------
\begin{figure}[htbp]
\centering
  \input{chapter9/figures/figure-obj_code_gen_exp2_step1}
  \caption{例9.7人工翻译过程}
	\label{fig:9-9}
\end{figure}
%-------------------------------------------

第二步，人工翻译目标代码。根据题意，只有一个寄存器R，初始状态为空。

第(1)个四元式，给$t_1$分配寄存器，生成目标代码\ding{172}LD R, $a$ \ding{173}GT R, $b$，GT为>的操作码，表示比较R中内容是否大于$b$。修改描述表RDL，R保存$t_1$。

第(2)个四元式，if四元式当$t_1$为假时，跳转到第(6)个四元式的第一条目标代码，但在生成if四元式的目标代码时，跳转位置未知，生成假跳目标代码\ding{174}FJ R, ?，?表示待返填。跳转位置要等第(6)个四元式目标代码生成后，才能填写，因此将带问号的目标代码编号\ding{174}保存到SEM中。第(2)个四元式是一个基本块的出口，需要将所有寄存器内容释放，$t_1$不活跃，不需要保存到内存。修改描述表RDL，R空闲。

第(3)个四元式，给$t_2$分配寄存器，将$a$读入寄存器R，进行$a+b$运算，生成目标代码\ding{175}LD R, $a$ \ding{176}ADD R, $b$。修改描述表RDL，R保存$t_2$。

第(4)个四元式，运算对象$t_2$在寄存器中，乘法运算可交换，进行“主动释放”，且$t_2$不活跃，不需要保存到内存，直接进行$t_2$*c运算，生成目标代码\ding{177}MUL R, $c$。修改描述表RDL，R保存$x$。

第(5)个四元式，else四元式是基本块出口，需要清空寄存器。根据约定，用户定义变量在基本块出口是活跃的，需要保存到内存，生成目标代码\ding{178}ST R, $x$。同时该四元式表示无条件跳转，跳转到ie四元式的下一条，跳转位置未知，生成目标代码\ding{179}JMP , ?，将带问号的目标代码编号\ding{179}保存到SEM中，?待返填。

第(6)个四元式，生成的第一条目标代码编号为\ding{180}，注意第(2)个四元式的跳转位置为第(6)个四元式的第一条目标代码，所以将\ding{180}填入第一个返填位置：从SEM队列中找到编码\ding{174}，然后回填到编码为\ding{174}的目标代码的？处。之后生成第(6)个四元式的目标代码\ding{180}LD R, $a$ \ding{181}MUL R, $b$。修改描述表RDL，R保存$t_3$。

第(7)个四元式，与前一例类似，减法运算不可交换，第二运算对象$t_3$需要保存到内存供减法中使用，生成目标代码\textcircled{\footnotesize 11}ST R, $t_3$ \textcircled{\footnotesize 12}LD R, 5 \textcircled{\footnotesize 13}SUB R, $t_3$。修改描述表RDL，R保存$x$。

第(8)个四元式，作为基本块出口，要释放寄存器，用户定义变量x保存到内存，生成目标代码\textcircled{\footnotesize 14}ST R, $x$。下一条目标代码编号为15，填入第二个返填位置：从SEM队列中找到编码\ding{179}，然后回填到编码为\ding{179}的目标代码的?处。

注意，要及时处理跳转地址返填。在实践中，先返填，后编写跳转指令。如生成第五个四元式对应的目标代码\ding{178}、\ding{179}时，先不生成\ding{179}的指令，先将下一条目标代码的编号\ding{180}返填，再编写跳转指令\ding{179}。因为编写跳转指令后，要将编号压栈，栈顶不是\ding{174}，是\ding{179}，返填时就会出现问题。

填表结果如下图\ref{fig:9-10}：

%-------------------------------------------
\begin{figure}[htbp]
\centering
  \input{chapter9/figures/figure-obj_code_gen_exp2_result}
  \caption{例9.7填表结果}
	\label{fig:9-10}
\end{figure}
%-------------------------------------------

上述例题中，都是通过人工的方式翻译目标代码，接下来系统介绍生成目标代码。
\label{ex:9-7}
\end{example}

%----------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------
\section{目标代码生成算法设计}

通过两道例题总结算法。

%----------------------------------------------

\begin{example}
给定如下基本块，写出四元式序列，进行DAG优化，完成单寄存器目标代码生成：

\begin{tabular}{cl}
&$ a = 10 + 5$\\
&$ x = 10 + 5 - y$\\
&$ y = a * x$
\end{tabular}

解：
第一步，生成四元式序列如下:

\begin{tabular}{ccccr}
\ding{172}&( $+$, & 10,    & 5, & $t_1$ ) \\
\ding{173}&( $=$, & $t_1$, & \_\_,& $a$ ) \\
\ding{174}&( $+$, & 10,    & 5, & $t_2$ ) \\
\ding{175}&( $-$, & $t_2$, & $y$, & $t_3$ ) \\
\ding{176}&( $=$, & $t_3$, & \_\_,& $x$ ) \\
\ding{177}&( $*$, & $a$,     & $x$ ,& $t_4$ ) \\
\ding{178}&( $=$, & $t_4$, & \_\_,& $y$ )
\end{tabular}

第二步，画DAG图如图\ref{ex:9-11}:

%-------------------------------------------
\begin{figure}[h]
  \centering
  \input{chapter9/figures/figure-obj_code_gen_alg_exp1_DAG}
  \caption{例9.8 DAG图}
	\label{fig:9-11}
\end{figure}
%-------------------------------------------

第三步，得到优化后的四元式序列如下。括号中待填的是活跃信息。

\begin{tabular}{ccccr}
\ding{172}&( $=$, & 15,& \_\_,  & $a$( ) ) \\
\ding{173}&( \_\_,& 15,& $y$( ),& $x$( ) ) \\
\ding{174}&( $*$, & 15,& $x$( ),& $y$( ) ) \\
\end{tabular}

第四步，生成目标代码。
(1) 标活跃信息：

给变量a, x, y标活跃信息，由于均为用户定义变量，初值均为y，逆序填活跃信息。对最后一个四元式，填结果单元y的活跃信息，先从符号表主表的信息项读取当前状态y，在符号表中返填n；填运算对象x的活跃信息，先从符号表主表的信息项读取当前状态y，在符号表中返填y。类似地，完成活跃信息的填写，结果如下：

\begin{tabular}{ccccr}
\ding{172}&( $=$, & 15, &\_\_,  &$a(\rm y)$ ) \\
\ding{173}&( \_\_,& 15, &$y(\rm n)$,&$x(\rm y)$ ) \\
\ding{174}&( $*$, & 15, &$x(\rm y)$,&$y(\rm y)$ ) \\
\end{tabular}

\begin{tabular}{lccc}
&$a$ &| &n \\

&$x$ &| &n \\

&$y$ &| &y
\end{tabular}

(2) 目标指令生成：

第一个四元式，是赋值四元式，生成模板为：LD R, \dots ; ST R, \dots 给$a$分配寄存器，生成目标指令：LD R, 15
模板第二条滞后生成。

第二个四元式，是运算四元式，生成模板为LD R, \dots ; $\widetilde{\omega}$ R, \dots ; ST R, \dots。给x分配寄存器，运算对象不在寄存器中，由于$a$是活跃变量，需要保存到内存，生成ST指令，生成目标指令ST R, $a$; $\rm LD\ R_m\ 15$; SUB R, $y$，模板第三条滞后生成。

第三个四元式，给$y$分配寄存器，寄存器中的值为第二运算对象，乘法运算可交换，模板第一条可省去，$x$主动释放寄存器，由于$x$是活跃变量，需要保存到内存，生成ST指令，生成目标指令为ST R, $x$; MUL R, 15。一个基本块结束，释放寄存器，由于$y$是活跃变量，需要保存到内存，生成目标指令ST R, $y$。结果如下：

目标指令生成

\begin{tabular}{llll}
\ding{172} & LD  & R, & 15 \\
\ding{173} & ST  & R, & $a$ \\
\ding{174} & LD  & R, & 15 \\
\ding{175} & SUB & R, & $y$ \\
\ding{176} & ST  & R, & $x$ \\
\ding{177} & MUL & R, & 15 \\
\ding{178} & ST  & R, & $y$ \\
\end{tabular}
\label{ex:9-8}
\end{example}

%----------------------------------------------

%----------------------------------------------

\begin{example}
给定如下基本块，写出四元式序列，进行DAG优化，完成单寄存器目标代码生成：

\begin{tabular}{cl}
&$y = 1$\\
&$x = 10 + 5 - y$\\
&$y = a * x$\\
&$b = a + b$\\
\end{tabular}

第一步，生成四元式序列如下:

\begin{tabular}{llllr}
\ding{172} & ( $=$, & 1,      &\_\_,  &$y$) \\
\ding{173} & ( $+$, & 10,     &5,   &$t_1$) \\
\ding{174} & ( $-$, & $t_1$,  &$y$,   &$t_2$) \\
\ding{175} & ( $=$, & $t_2$,  &\_\_,  &$x$) \\
\ding{176} & ( $*$, & $a$,      &$x$,   &$t_3$) \\
\ding{177} & ( $=$, & $t_3$,  &\_\_,  &$y$) \\
\ding{178} & ( $+$, & $a$,      &$b$,   &$t_4$) \\
\ding{179} & ( $=$, & $t_4$,  &\_\_,  &$b$) \\
\end{tabular}

第二步，画DAG图如下图\ref{fig:9-12}:

%-------------------------------------------
\begin{figure}[h]
  \centering
  \input{chapter9/figures/figure-obj_code_gen_alg_exp2_DAG}
  \caption{例9.9 DAG图}
	\label{fig:9-12}
\end{figure}
%-------------------------------------------

第三步，得到优化后的四元式序列如下，括号中待填的是活跃信息。

\begin{tabular}{llllr}
\ding{172} & ( $-$, & 15,   & 1,    & $x$( ) ) \\
\ding{173} & ( $*$, & $a$( ), & $x$( ), & $y$( ) ) \\
\ding{174} & ( $+$, & $a$( ), & $b$( ), & $b$( ) ) \\
\end{tabular}

第四步，生成目标代码。（标活跃信息，目标指令生成）

\begin{tabular}{llllr}
\ding{172} & ( $-$, & 15,   &1,     & $x(\rm y)$ ) \\
\ding{173} & ( $*$, & $a(\rm y)$, & $x(\rm y)$, & $y(\rm y)$ ) \\
\ding{174} & ( $+$, & $a(\rm y)$, & $b(\rm n)$, & $b(\rm y)$ ) \\
\end{tabular}

\begin{tabular}{clll}
&$x$ &| &n \\
&$y$ &| &n \\
&$a$ &| &y \\
&$b$ &| &y \\
\end{tabular}

目标指令生成

\begin{tabular}{lllr}
\ding{172} & LD  & R, & 15 \\
\ding{173} & SUB & R, & 1 \\
\ding{174} & ST  & R, & $x$ \\
\ding{175} & MUL & R, & $a$ \\
\ding{176} & ST  & R, & $y$ \\
\ding{177} & LD  & R, & $a$ \\
\ding{178} & ADD & R, & $b$ \\
\ding{179} & ST  & R, & $b$ \\
\end{tabular}

总结算法之前，先要明确目标代码的生成要点和生成环境。
\label{ex:9-9}
\end{example}

%----------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\subsection{目标代码生成要点和生成环境}

$\bigstar$ \textbf{生成要点}

\begin{enumerate}
\item \textbf{目标代码生成是在一个基本块上进行的：}

(1)	入口：寄存器空闲；

(2)	出口：释放寄存器。如\ref{ex:9-7}中编号7和14的目标代码。

\item \textbf{目标代码生成是以一个一个四元式为单位进行的：}

(1)	表达式、赋值四元式：首先对结果变量申请寄存器；然后编写目标指令；并修改描述表。

(2)	转向四元式：首先保存占用寄存器的活跃变量值（转向四元式是基本块出口）；然后再编写跳转指令；同时记住待返填地址。先保存活跃变量，还是先编写跳转指令，可以自己设计。

注意：释放寄存器时，编写存储指令，保存占有寄存器的活跃变量值，通常发生在如下两个时刻：

(1)	为结果变量申请寄存器时。强迫释放时，要先保存寄存器内活跃变量。

(2)	基本块出口时。出口需要释放寄存器。

\end{enumerate}

$\bigstar$ \textbf{生成环境}

\begin{enumerate}
\item \textbf{虚拟机：}单一寄存器R；指令形式p: (op R, M)，M表示变量内存地址

含义：R :=(R) op (M) 或R := op (M)

\item \textbf{表、区和栈：}
QY[q]——四元式区（附有变量的活跃信息）；

OBJ[p]——目标代码区；

SEM[m]——语义栈（登记待返填的目标地址）；

SYMBL[i]——符号表；

RDL[R]——寄存器描述表；

当RDL=0时，表示寄存器R空闲；当RDL=X时，表示寄存器R被变量X占用。

\item \textbf{变量和函数：}
CODE (op, R, M; …) ——（送代码函数）把目标代码送目标区；

BACK ($p_i$, $p_k$) ——（返填函数）把地址$p_k$返填到地址$p_i$中，$p_k$表示跳转到的地址，$p_i$表示待填地址。

\end{enumerate}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{表达式四元式目标代码生成算法}

设当前扫描的四元式q: ($\omega$ B C A)，是操作四元式，对应包含三条目标指令的模板。

(1)	为结果单元A预分配寄存器，编写目标指令:

\ding{172} 当RDL==0，则CODE( LD R, B ; $\widetilde{\omega}$ R, C)。$\widetilde{\omega}$表示算符$\omega$对应的操作码。

\ding{173} 当RDL==B，则

若B\rm (y)，则CODE( ST R, B ; $\widetilde{\omega}$ R, C)；

否则CODE($\widetilde{\omega}$ R, C)。

\ding{174} 当RDL==C，且$\omega$可交换，则

若C\rm (y)，则 CODE( ST R, C ; $\widetilde{\omega}$ R, B)；

否则CODE($\widetilde{\omega}$ R, B)。

\ding{175} 当RDL==D（上述三种情况之外）则

若D\rm (y)，则CODE( ST R, D ; LD R, B ; $\widetilde{\omega}$ R, C)；

否则CODE( LD R, B ; $\widetilde{\omega}$ R, C)

(2)	变量A登录到描述表中：RDL := A；

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{赋值四元式目标代码生成算法}

设当前四元式q: (= B \_\_ A)

(1)	为A预分配寄存器，编写目标指令：

\ding{172} 当RDL==0，则CODE( LD R, B)；此时R寄存器的标志是A。

\ding{173}当RDL==B，则

若B\rm (y)，则CODE( ST R, B)。

此时B在寄存器里，但不一定在内存里，所以需要判断B是否活跃。若B活跃，寄存器被清空时要保证B写回内存；若B不活跃，则不需要保存，直接修改描述表即可。

\ding{174} 当RDL==D (D != B, D != A)则

若D\rm (y)，则CODE( ST R, D ; LD R, B)；

否则CODE( LD R, B)。

(2)	变量A登录到描述表中：RDL := A;

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{条件语句四元式目标代码生成算法}

有了表达式四元式和赋值四元式目标代码生成算法，接下来介绍条件语句和循环语句目标代码生成的算法。if语句、while语句等从语义上实现的是一种逻辑，对于不同条件，有不同的处理，这类逻辑在if语句中，主要关注if四元式、el四元式和ie四元式。为了简化说明，假设不存在if嵌套，其他四元式均顺序执行，为表达式四元式或赋值四元式，前面已经介绍过目标代码生成的算法。接下来主要要解决的问题是，对于if四元式、el四元式和ie四元式，如何生成目标指令。

回顾例\ref{ex:9-7}，if四元式在中间代码级别语义为假跳，即当$t_1$为假时，跳转到el四元式的下一句。目标代码的语义与中间代码等价，if语句的目标指令语义同样对应假跳。再看el四元式，中间代码语义为无条件跳，对应目标指令的无条件跳。对ie四元式，在中间代码级别是作为一个跳转标志，没有语义，因此没有对应的目标指令生成。

如：if($a>b$)\enspace$x=(a+b)*c$; else $x=5-a*b$;

%-------------------------------------------
\begin{figure}[h]
  \centering
  \input{chapter9/figures/figure-obj_code_gen_proc_exp1}
  \caption{目标代码生成示例}
	\label{fig:9-13}
\end{figure}
%-------------------------------------------

根据上例，总结得到条件语句四元式目标代码生成算法，SEM采用栈结构，先返填，后编写跳转指令。

$\bigstar$ \textbf{条件语句的四元式结构：}

设条件语句：if(E) S1; else S2;

则四元式结构如图\ref{fig:9-14}：

%-------------------------------------------
\begin{figure}[H]
  \centering
  \input{chapter9/figures/figure-obj_code_gen_proc_exp1_quat}
  \caption{四元式结构}
	\label{fig:9-14}
\end{figure}
%-------------------------------------------

注意：q2(el \_\_ \_\_ \_\_)的下面就是S2语句的入口。

$\bigstar$ \textbf{算法设计：}
\begin{enumerate}
\item 设当前四元式q: (if B \_\_ \_\_)

(1)	若RDL==0（寄存器为空），则CODE(LD R, B ; FJ R, \_\_); PUSH(p);

p为待返填的目标代码(FJ R, \_\_)的编号（地址）。

(2)	若RDL==B，

\ding{172} 若B\rm (y)，则CODE(ST R, B ; FJ R, \_\_)；否则CODE(FJ R, \_\_);

if语句为基本块出口，要释放寄存器，B在寄存器R中，若B活跃，要保存到内存。

\ding{173} PUSH(p); RDL:=0;

(3)	若RDL==D (D != B)

\ding{172} 若D\rm (y)，则CODE(ST R, D ; LD R, B ; FJ R, \_\_)；否则CODE(LD R, B ; FJ R, \_\_);

\ding{173} PUSH(p); RDL:=0;

\item 设当前四元式q: (el \_\_ \_\_ \_\_)

else语句有两个功能：\ding{172}它的下一条语句是if语句跳转到的位置；\ding{173}它本身是跳转语句，跳转到条件语句的出口位置。且else语句是一个基本块的出口，需要释放寄存器。

(1)	当RDL==X且X\rm (y)，则CODE(ST R, X ; ); RDL:=0

(2)	返填转向地址：POP(p'); BACK(p', p+2)；POP函数表示SEM栈顶地址弹到p'，BACK函数表示把地址p+2填入p'中。

\ref{ex:9-7}中SEM若使用栈结构，对于第(5)个四元式，未生成对应目标代码⑧时，执行POP(p')函数，根据SEM栈顶元素p'（编号\ding{174}），找到对应的目标指令。下一步执行BACK(p', p+2)，p'是待返填的目标指令编号，对于条件语句，在编号为p的目标指令之后，还有编号为p+1的无条件跳转目标指令JMP ?，跳转的目标位置在JMP指令之后，即编号为p+2，因此将p+2返填回p'。此处，p为当前指令编号\ding{178}，p+2为\ding{180}，即将\ding{180}返填回\ding{174}对应的目标代码。\ding{179}目标代码还未生成，先将\ding{180}返填回\ding{174}。

(3)	编写转向指令，CODE(JMP \_\_, \_\_); PUSH(p)

\item 设当前四元式q: (ie \_\_ \_\_ \_\_)

if end语句为基本块出口，需要释放寄存器。

(1)	当RDL==X 且X\rm (y)，则CODE(ST R, X ; ); RDL:=0

(2)	返填转向地址：POP(p'); BACK(p', p+1)。

\ref{ex:9-7}中，对于第(8)个四元式，已经生成编号14的目标代码，p为编号14，执行POP(p')，当前SEM栈顶元素p'为\ding{179}。下一步执行BACK(p', p+1)，因为(ie \_\_ \_\_ \_\_)生成目标指令中没有JMP指令，因此跳转目标位置的编码为p+1为编号15，将编号15返填回\ding{179}对应的目标代码。

\end{enumerate}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{循环语句四元式目标代码生成算法}

有了条件语句四元式目标代码生成的基础，循环语句就容易理解了。

%----------------------------------------------

\begin{example}
写出给定语句的目标代码：

$\text{while}\ (a > b) \enspace x = (a + b) * c;$

解：

第一步，写出对应四元式序列，划分基本块，并标注活跃信息。

第二步，生成目标代码。

第(1)个四元式，每次循环结束后，都要跳转到该位置，再进行条件判断，这个语句本身不生成相应的目标代码，但是它的下一条语句是循环的开始位置，所以要将这个语句的编号\ding{172}压入SEM栈中，为了后面跳转到下一次循环时，找到跳转位置。

第(2)个四元式，与前面例题类似，生成目标代码\ding{172}LD R, $a$ \ding{173}GT R, $b$。

第(3)个四元式，do语句判断$t_1$为假时，进行跳转，又因该四元式为基本块出口，需要释放寄存器，$t_1$非活跃，不需要进行保存，生成目标指令\ding{174} FJ R, ?，跳转到第(6)个四元式生成的第一条目标代码，现在目标代码编号未知，将\ding{174}压入SEM栈，?待返填。

第(4)、(5)个四元式，与前面例题类似，分别生成目标代码\ding{175}LD R, ? \ding{176}ADD R, $b$和\ding{177}MUL R, $c$。

第(6)个四元式，是基本块出口，需要释放寄存器，保存寄存器R中的活跃变量$x$到内存中，生成目标代码\ding{178}ST R, $x$；同时也是跳转语句，跳转到循环体的开始。下一条目标代码编号为\ding{180}，返填回SEM栈顶\ding{174}对应的目标代码。之后生成目标代码\ding{179}JMP \_\_, ?，跳转到循环的开始，?待返填。此时SEM栈顶为\ding{172}，填\ding{179}对应的目标代码中。

注意，在实践中，先返填，后编写跳转指令，即在生成\ding{179}时，先将\ding{180}返填回SEM栈顶元素\ding{174}中，再将\ding{172}填入\ding{179}中。

如：$\text{if}(a>b) \enspace x=(a+b)*c; \enspace \text{else} x=5-a*b;$

%-------------------------------------------
\begin{figure}[h]
  \centering
  \input{chapter9/figures/figure-obj_code_gen_proc_exp2}
  \caption{目标代码生成示例}
	\label{fig:9-15}
\end{figure}
%-------------------------------------------
\label{ex:9-10}
\end{example}

%----------------------------------------------

$\bigstar$ \textbf{算法设计}
\begin{enumerate}
\item 设当前四元式q: (wh \_\_ \_\_ \_\_)，这是一个基本块的入口，也是一个循环的入口。

PUSH(p); 将当前要生成的目标指令编号压栈。

\item 设当前四元式q: (do B \_\_ \_\_)，do语句判断B是否为假，为假则跳转。

(1)	当RDL==0，则CODE(LD R, B ; FJ R, \_\_); PUSH(p)
将指令编号或地址压入SEM栈，等待返填。

(2)	当RDL==B，则

\ding{172} 若B\rm (y)，则CODE(ST R, B ; FJ R, \_\_)；否则CODE(FJ R, \_\_);

\ding{173} PUSH(p); RDL:=0;

在(1)中未改变寄存器状态，始终为空，(2)中寄存器状态原为B，需要释放寄存器。
(3)	当RDL==D (D != B)，则

\ding{172} 若D\rm (y)，则CODE(ST R, D ; LD R, B ; FJ R, \_\_)；否则CODE(LD R, B ; FJ R, \_\_);

\ding{173} PUSH(p); RDL:=0;

\item 设当前四元式q: (we \_\_ \_\_ \_\_)，作用1：标记结束；作用2：跳转到while开始。

(1)	若RDL==X 且X\rm (y)，则CODE(ST R, X ; ); 

(2)	RDL:=0;

(3)	返填转向地址：POP(p'); BACK(p', p+2)。

\ref{ex:9-10}，在第(6)个四元式中，已经生成目标代码\ding{178}，当前p为编号\ding{178}，执行POP(p')，根据SEM栈顶元素p'（编号\ding{174}），找到对应的目标指令。下一步执行BACK(p', p+2)，p'是待返填的目标指令编号\ding{174}，在编号为p的目标指令之后，还有编号为p+1的无条件跳转目标指令JMP ?，跳转的目标位置在JMP指令之后，即编号为p+2，因此将p+2返填回p'。p+2为\ding{180}，将\ding{180}返填回\ding{174}对应的目标代码。

(4)	POP(p');

\ref{ex:9-10}中，将SEM栈顶地址\ding{172}弹入p'。

(5)	CODE(JMP \_\_,p');

\ref{ex:9-10}中，跳转到p'，将\ding{172}填入\ding{179}对应的目标代码中。

\end{enumerate}

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{一个简单代码生成器的实现}

下面给出的简单代码生成器的主控程序流程图\ref{fig:9-16}。

首先进行预处理，划分基本块。接下来，对一个基本块进行处理，生成变量活跃信息，顺序遍历四元式，编写目标指令，直到到达基本块出口，释放寄存器，并跳转到取下一基本块，继续执行上述操作，直到取不到下一基本块，表示处理结束。主控程序不唯一，可以自行设计。

%-------------------------------------------
\begin{figure}[h]
  \centering
  \input{chapter9/figures/figure-flowchart_of_main_control_simple_code_gen}
  \caption{主控程序流程图}
	\label{fig:9-16}
\end{figure}
%-------------------------------------------

下面介绍一个表达式与赋值四元式生成目标代码的例子，这些语句都是顺序执行，比较简单。

%----------------------------------------------

\begin{example}
设有赋值语句（四元式序列）：$x = a * (a + b - d); \enspace a = (a + b) / 2; \enspace y = 5;$

解：

第一步，生成四元式序列，这里只有一个基本块，标注活跃信息。

第二步，顺序遍历四元式，编写目标指令。

第(1)个四元式，给$t_1$分配寄存器，生成目标代码\ding{172}LD R, $a$ \ding{173}ADD R, $b$。

第(2)个四元式，给$t_2$分配寄存器，运算对象$t_1$在寄存器中，且$t_1$活跃，需要保存到内存，生成目标代码\ding{174}ST R, $t_1$ \ding{175}SUB R, $d$。

第(3)个四元式，乘法运算可交换，运算对象$t_2$在寄存器中，且$t_2$非活跃，直接进行计算，生成目标代码\ding{176}MUL R, $a$。

第(4)个四元式，给$a$分配寄存器，运算对象$t_1$不在寄存器中，原本寄存器中的$x$活跃，需要保存到内存，生成目标代码\ding{177}ST R, $x$ \ding{178}LD R, $t_1$ \ding{179}DIV R, 2。

第(5)个四元式，给$y$分配寄存器，寄存器中的$a$活跃，需要保存到内存，生成目标代码\ding{180}ST R, $a$ \ding{181}LD R, 5。到达基本块出口，释放寄存器，且$y$活跃，需要保存到内存，生成目标代码\textcircled{\footnotesize 11}ST R, $y$。

第(3)个四元式中的$a$是非活跃的，活跃的定义是从当前到下一个定义点之间有应用点，而变量$a$，第(4)个四元式是它的定义点，当前在第(3)个四元式，中间没有其他应用点，因此它是非活跃的。

填表结果如下图\ref{fig:9-17}：

%-------------------------------------------
\begin{figure}[htbp]
  \centering
  \input{chapter9/figures/figure-main_control_simple_code_gen_exp1_step1
  }
  \caption{例9.11寄存器分配填表结果}
	\label{fig:9-17}
\end{figure}
  %-------------------------------------------
\label{ex:9-11}
\end{example}

%----------------------------------------------

\begin{example}
给定如下语句，写出四元式序列，进行DAG优化，完成单寄存器目标代码生成。

$\text{if}\ (a > b) \enspace x = (a + b) / (c - d) + (a + b)$;

第一步，生成四元式序列如下：

\begin{tabular}{llllr}
\ding{172} & ( $>$,  &  $a$,    & $b$,     & $t_1$) \\
\ding{173} & ( if, &  $t_1$,& \_\_,    & \_\_) \\
\ding{174} & ( $+$,  &  $a$,    & $b$,     & $t_2$) \\
\ding{175} & ( $-$,  &  $c$,    & $d$,     & $t_3$) \\
\ding{176} & ( $/$,  &  $t_2$,& $t_3$, & $t_4$) \\
\ding{177} & ( $+$,  &  $a$,    & $b$,     & $t_5$) \\
\ding{178} & ( $+$,  &  $t_4$,& $t_5$, & $t_6$) \\
\ding{179} & ( $=$,  &  $t_6$,& \_\_,    & $x$) \\
\ding{180} & ( end,&  \_\_,   & \_\_,    & \_\_) \\
\end{tabular}

第二步，划分基本块，对第二个基本块，画DAG图如下\ref{fig:9-18}:

%-------------------------------------------
\begin{figure}[h]
  \centering
  \input{chapter9/figures/figure-main_control_simple_code_gen_exp1_step2_DAG}
  \caption{例9.12 DAG图}
	\label{fig:9-18}
\end{figure}
%-------------------------------------------

第三步，写出优化后四元式如下图。括号中是活跃信息。

%------y-------------------------------------
\begin{figure}[h]
  \centering
  \input{chapter9/figures/figure-main_control_simple_code_gen_exp1_step3}
  \caption{例9.12 活跃信息}
	\label{fig:9-19}
\end{figure}
%-------------------------------------------

\begin{tabular}{llllr}
\ding{172} & ( $>$,  & $a\rm (y)$,    & $b\rm (y)$,    & $t_1$\rm (y) ) \\
\ding{173} & ( if, & $t_1$(n),& \_\_,      & \_\_ ) \\
\ding{174} & ( $+$,  & $a$\rm (y),    & $b$\rm (y),    & $t_2$\rm (y) ) \\
\ding{175} & ( $-$,  & $c$\rm (y),    & $d$\rm (y),    & $t_3$\rm (y) ) \\
\ding{176} & ( $/$,  & $t_2$\rm (y),& $t_3$(n),& $t_4$\rm (y) ) \\
\ding{177} & ( $+$,  & $a$(n),    & $b$(n),    & $t_5$\rm (y) ) \\
\ding{178} & ( end,& \_\_,      & \_\_,      & \_\_ ) \\
\end{tabular}

第四步，生成目标指令。

目标指令

\begin{tabular}{lllr}
\textcircled{\footnotesize 1}   & LD  &  R, & $a$ \\
\textcircled{\footnotesize 2}   & GT  &  R, & $b$ \\
\textcircled{\footnotesize 3}   & FJ  &  R, & ? \\
\textcircled{\footnotesize 4}   & LD  &  R, & $a$ \\
\textcircled{\footnotesize 5}   & ADD &  R, & $b$ \\
\textcircled{\footnotesize 6}   & ST  &  R, & $t_2$ \\
\textcircled{\footnotesize 7}   & LD  &  R, & $c$ \\
\textcircled{\footnotesize 8}   & SUB &  R, & $d$ \\
\textcircled{\footnotesize 9}   & ST  &  R, & $t_3$ \\
\textcircled{\footnotesize 10}  & LD  &  R, & $t_2$ \\
\textcircled{\footnotesize 11}  & IV  &  R, & $t_3$ \\
\textcircled{\footnotesize 12}  & ADD &  R, & $t_2$ \\
\textcircled{\footnotesize 13}  & ST  &  R, & $x$ \\
\end{tabular}

\label{ex:9-12}
\end{example}

%----------------------------------------------
